package com.wm.algorithm.linked;

import com.wm.algorithm.linked.entity.ListNode;

/**
 * @ClassName:SimpleLinked
 * @Description: 链表简单程度
 * @Author:Deamer
 * @Date:2022/2/2 22:42
 **/
public class SimpleLinked {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(4);

        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(3);
        head2.next.next = new ListNode(4);
        ListNode tmpNode = head;
        ListNode tmpNode2 = head2;
        System.out.println("转换之前：");
        while (head != null) {
            System.out.print(head.val + "\t");
            head = head.next;
        }
        System.out.println();
        while (head2 != null) {
            System.out.print(head2.val + "\t");
            head2 = head2.next;
        }
        ListNode newNode = mergeTwoLists(tmpNode, tmpNode2);
        System.out.println();
        System.out.println("转换之后：");
        while (newNode != null) {
            System.out.print(newNode.val + "\t");
            newNode = newNode.next;
        }
    }

    /**
     * 234. 回文链表
     * https://leetcode.cn/problems/palindrome-linked-list/
     * 方法2：双指针-快慢指针
     * 思路：使用快慢指针，快指针比慢指针快走一倍的步数，目的找到右半个链表的头节点，反转此半个链表，然后与左半个链表进行数值比对，以此来判断是否是回文链表。
     * 这里需要注意链表节点奇偶数的情况，因为都是从head节点开始跳，所以奇数节点链表，fast跳偶数步到达尾结点，此时head!=null，head.next==null，这是我们一定要让
     * slow再走一步，也就是让slow节点指向最中间的位置时再往下走一步；偶数节点链表，fast跳偶数步最终指向null，此时slow就是我们要找的节点。
     *
     * @param head
     * @return
     */
    // O(n)/O(1)
    public boolean isPalindrome2(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast != null) {
            slow = slow.next;
        }
        ListNode left = head;
        ListNode right = reverse(slow);
        while (right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }

    // 反转列表-迭代
    private ListNode reverse(ListNode node) {
        ListNode pre = null, cur = node;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 234. 回文链表
     * https://leetcode.cn/problems/palindrome-linked-list/
     * 方法1：转化为二叉树的后续遍历+双指针
     * 思路：将头节点转化为左右指针节点，右指针递归到达链表末端，然后利用双指针的方式，将左右指针指向的值进行比较大小，不一样大说明不是回文
     *
     * @param head
     * @return
     */

    // 左指针
    ListNode left;

    // O(n)/O(n)
    public boolean isPalindrome(ListNode head) {
        left = head;
        return traverse(head);
    }

    private boolean traverse(ListNode right) {
        if (right == null) {
            return true;
        }
        // 后序遍历代码
        boolean res = traverse(right.next);
        res = res && left.val == right.val;
        left = left.next;
        return res;
    }


    /**
     * 剑指 Offer II 024. 反转链表
     * https://leetcode.cn/problems/UHnkqh/
     * 方法：迭代
     *
     * @param head
     * @return
     */
    // O(n)/O(1)
    public ListNode reverseList5(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 剑指 Offer 24. 反转链表
     * https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/
     * 方法2：迭代
     *
     * @param head
     * @return
     */
    // O(n)/O(1)
    public ListNode reverseList4(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // cur为null
        return pre;
    }


    /**
     * 剑指 Offer 24. 反转链表
     * https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/
     * 方法1：递归
     *
     * @param head
     * @return
     */
    // O(n)/O(n)
    public ListNode reverseList3(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode last = reverseList3(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }


    /**
     * 反转链表的前N个节点
     * 方法：递归
     * 思路：记录一个后驱节点，将N个节点反转之后，反转后的尾结点接到第N+1个节点的后面
     *
     * @param head
     * @param n
     * @return
     */
    // 反转以 head 为起点的 n 个节点，返回新的头结点
    ListNode successor = null; // 后驱节点

    public ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // 记录第 n + 1 个节点
            successor = head.next;
            return head;
        }
        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode last = reverseN(head.next, n - 1);

        head.next.next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head.next = successor;
        return last;
    }

    /**
     * 206. 反转链表
     * https://leetcode.cn/problems/reverse-linked-list/description/
     * 方法2：迭代
     * 思路：在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。
     * 在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
     *
     * @param head
     * @return
     */
    // O(n)，其中 n 是链表的长度。需要遍历链表一次
    // O(1)
    public ListNode reverseList2(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            // 前节点覆盖下一个节点，实现一次指针反转
            ListNode next = cur.next;
            cur.next = pre;
            // 继续前进
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 206. 反转链表
     * https://leetcode.cn/problems/reverse-linked-list/description/
     * 方法1：递归
     * 思路：从链表的第二个节点开始，一直追溯到列表的尾结点，返回尾结点即反转后链表的头节点，然后处理尾结点，即将原来链表的第二个节点下一个节点指向原来头节点，
     * 原来头节点下一个节点指向null
     *
     * @param head
     * @return
     */
    // O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
    // O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。
    public ListNode reverseList(ListNode head) {
        // 如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可
        if (head == null || head.next == null) {
            return head;
        }
        ListNode last = reverseList(head.next);
        // 处理新反转后链表的尾结点，即原来正数第二个节点，反转后的倒数第二个节点
        head.next.next = head;
        head.next = null;
        return last;
    }

    /**
     * 160. 相交链表
     * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
     * 方法二：去头补长
     * 思路：预先计算两条链表的长度，长度长的链表先去除前面多出来的节点，然后两条链表一起遍历
     *
     * @param headA
     * @param headB
     * @return
     */
    // O(n)/O(1)
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        // P1指向A链表头节点，P2指向B链表头节点
        ListNode p1 = headA, p2 = headB;
        int lenA = 0, lenB = 0;
        // 计算两条链表的长度
        while (p1 != null) {
            lenA++;
            p1 = p1.next;
        }
        while (p2 != null) {
            lenB++;
            p2 = p2.next;
        }
        // 让 p1 和 p2 到达尾部的距离相同
        p1 = headA;
        p2 = headB;
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                p1 = p1.next;
            }
        } else {
            for (int i = 0; i < lenB - lenA; i++) {
                p2 = p2.next;
            }
        }
        // 看两个指针是否会相同，p1 == p2 时有两种情况：
        // 1、要么是两条链表不相交，他俩同时走到尾部空指针
        // 2、要么是两条链表相交，他俩走到两条链表的相交点
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }


    /**
     * 160. 相交链表
     * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
     * 方法一：对称补长
     * 思路：让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。
     * 如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1
     *
     * @param headA
     * @param headB
     * @return
     */
    // O(n)/O(1)
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // P1指向A链表头节点，P2指向B链表头节点
        ListNode p1 = headA, p2 = headB;
        while (p1 != p2) {
            if (p1 != null) {
                p1 = p1.next;
            } else {
                p1 = headB;
            }
            if (p2 != null) {
                p2 = p2.next;
            } else {
                p2 = headA;
            }
        }
        return p1;
    }

    /**
     * 探测链表中是否有环，如果有环返回环的起点
     * 方法：双指针(快慢指针)
     * 当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        // 判断是否有环
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 快慢指针相遇
            if (slow == fast) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            // fast 遇到空指针说明没有环
            return null;
        }
        // 重新指向头结点
        slow = head;
        // 快慢指针同步前进，相交点就是环起点
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 判断链表中是否有环
     * 方法：双指针(快慢指针)
     * 每当慢指针 slow 前进一步，快指针 fast 就前进两步
     * 如果 fast 最终遇到空指针，说明链表中没有环；如果 fast 最终和 slow 相遇，那肯定是 fast 超过了 slow 一圈，说明链表中含有环。
     *
     * @param head
     * @return
     */
    // O(n)/O(1)
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 快慢指针相遇说明含有环
            if (fast == slow) {
                return true;
            }
        }
        // 不包含环
        return false;
    }

    /**
     * 876. 链表的中间结点
     * https://leetcode-cn.com/problems/middle-of-the-linked-list/
     * 方法：双指针(快慢指针)
     * 两个指针 slow 和 fast 分别指向链表头结点 head。
     * 每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。
     * 如果链表长度为偶数，也就是说中点有两个的时候，我们这个解法返回的节点是靠后的那个节点。
     *
     * @param head
     * @return
     */
    // O(n)/O(1)
    public ListNode middleNode(ListNode head) {
        // 快慢指针初始化指向head
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            // 快指针走两步
            fast = fast.next.next;
            // 慢指针走一步
            slow = slow.next;
        }
        // 慢指针指向中点
        return slow;
    }

    /**
     * 21. 合并两个有序链表
     * https://leetcode-cn.com/problems/merge-two-sorted-lists/
     * 方法：双指针(单链表)
     *
     * @param list1
     * @param list2
     * @return
     */
    // 时间复杂度：O(m+n) 空间复杂度：O(1)
    public ListNode mergeTwoLists3(ListNode list1, ListNode list2) {
        // 创建虚拟头节点，避免处理空指针的情况
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        ListNode p1 = list1, p2 = list2;
        while (p1 != null && p2 != null) {
            // 比较p1和p2两个指针，将值较小的节点接到p指针
            if (p1.val > p2.val) {
                p.next = p2;
                p2 = p2.next;
            } else {
                p.next = p1;
                p1 = p1.next;
            }
            // p指针不断前进
            p = p.next;
        }
        // 不要忘记处理某一个链表遍历为空的情况
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }
        return dummy.next;
    }

    /**
     * 83. 删除排序链表中的重复元素
     * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
     * 方法：快慢指针
     *
     * @param head
     * @return
     */
    // O(n)/O(1)
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            if (slow.val != fast.val) {
                slow.next = fast;
                slow = slow.next;
            }
            fast = fast.next;
        }
        // 注意断开slow与后面的重复元素的连接
        slow.next = null;
        // 注意这里返回的是head，不是slow
        return head;
    }

    /**
     * 21. 合并两个有序链表
     * https://leetcode-cn.com/problems/merge-two-sorted-lists/
     * 方法二：迭代
     *
     * @param list1
     * @param list2
     * @return
     */
    // 时间复杂度：O(m+n) 空间复杂度：O(1)
    public static ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        ListNode result = new ListNode(0);
        ListNode prev = result;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                prev.next = list1;
                list1 = list1.next;
            } else {
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;
        }
        // 合并后list1和list2最多只有一个未合并完，直接将链表末尾指向未合并完的链表即可
        prev.next = list1 == null ? list2 : list1;
        return result.next;
    }

    /**
     * 21. 合并两个有序链表
     * https://leetcode-cn.com/problems/merge-two-sorted-lists/
     * 方法一：递归
     *
     * @param list1
     * @param list2
     * @return
     */
    // 时间复杂度：O(m+n) 空间复杂度：O(m+n)
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        } else if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}
